/**
 * Alipay.com Inc.
 * Copyright (c) 2004-2021 All Rights Reserved.
 */
package primary.primary0;

import java.util.Arrays;

/**
 * @author congyun
 * @version S0034在排序数组中查找元素的第一个和最后一个位置.java, v 0.1 2021年08月22日 win10 Exp $
 */
public class S0034在排序数组中查找元素的第一个和最后一个位置 {
    /**
     * 100, 没啥好说的
     * 就二分查找了, 先用标准库找到符合的, 找到后往两边走, 复杂度应该可以接受
     */
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        int baseLoc = Arrays.binarySearch(nums, target);
        if(baseLoc < 0) return res;
        for(int i = baseLoc; i >= 0; i --){
            if(nums[i] == target){
                res[0] = i;
            }else{
                break;
            }
        }
        for(int i = baseLoc; i < nums.length; i++){
            if(nums[i] == target){
                res[1] = i;
            }else{
                break;
            }
        }
        return res;
    }
    /**
     * 先找比他大的第一个, 再找比他小的第一个?二分查找有点怪。
     */
}